package org.aplombh.java.awcing.basic.struct.link;

import java.util.Arrays;

public class MyLinkList {

    private static final int N = 100010;
    private int head;
    private int index;
    private int[] e;
    private int[] next;

    public MyLinkList() {
        clear();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();

        // 从头指针开始遍历
        for (int i = head; i != -1; i = next[i])
            builder.append(e[i]).append(" ");

        builder.append("\n");
        return builder.toString();
    }

    /**
     * 清空
     */
    public void clear() {
        // 指针下标
        index = 0;
        // 头指针
        head = -1;
        if (e == null)
            e = new int[N];
        if (next == null)
            next = new int[N];

        Arrays.fill(e, 0);
        Arrays.fill(next, 0);
    }

    /**
     * 在链头添加x （头插法）
     *
     * @param x 值
     */
    public void add(int x) {
        // 将数据存入e中
        e[index] = x;
        // 将next的指针指向头指针
        next[index] = head;
        // 头指针指向下一个指针的下标
        head = index++;
    }

    /**
     * 在第k个位置后添加x
     *
     * @param k k
     * @param x 值
     */
    public void addK(int k, int x) {
        // 将数据存入e
        e[index] = x;
        // 将该点next指针指向next[k]
        next[index] = next[k];
        // next[k] 的指针指向下一个指针的下标
        next[k] = index++;
    }

    /**
     * 移除第k个位置后的值
     *
     * @param k k
     */
    public void remove(int k) {
        if (k == -1)
            head = next[head];
        else
            next[k] = next[next[k]];
    }

    /**
     * 移除头节点
     */
    public void remove() {
        head = next[head];
    }
}
